package com.hqq.leetcode.array;

/**
 * BinarySort 二分查找
 * Description:
 * For a given sorted array (ascending order) and a target number,
 * find the first index of this number in O(log n) time complexity.
 * If the target number does not exist in the array, return -1.
 * Input:
 * [1, 2, 3, 3, 4, 5, 10],3
 * Output:
 * 2
 * <p>
 * Created by heqianqian on 2017/9/26.
 */
public class BinarySort {

    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 3, 3, 4, 5, 10};
        BinarySort sort = new BinarySort();
        int result = sort.binarySearch(array, 3);
        System.out.println(result);
    }

    /**
     * @param nums:   The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        int start = 0, end = nums.length;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if (start < nums.length && nums[start] == target) {
            return start;
        }
        return -1;
    }
}
